#include <stdio.h>
#include <iostream>
template<typename Comparable>
class BinarySearchTree{
private:
	struct BinaryNode{
		Comparable element;
		BinaryNode *left;
		BinaryNode *right;

		BinaryNode(const Comparable &theElement, BinaryNode *lt,BinaryNode*rt):element(theElement),
			left(lt),right(rt){
		}
	};
	BinaryNode *root; 

	void insert(const Comparable& x,BinaryNode *t)const{
		if( t == NULL)
			t = new BinaryNode(x,NULL,NULL); 
		else if( x < t->element)
			return insert(t->left);
		else if(x >t->element)
			return insert(t->right);
		else 
			; 
	}	
	void remove(const Comparable&x, BinaryNode *t)const{
		if (t==NULL)
			return ; 
		if( x<t->element )
			return remove(x,t->left); 
		else if ( x>t->element)
			return remove(x,t->right); 
		else if (t->left != NULL && t->right != NULL){
			t->element = findMini(t->right)->element; 
			remove(t->element,t->right);
		}
		else{
			BinaryNode *oldNode = t; 
			t = (t->left != NULL)?t->left : t->right; 
			delete oldNode; 
		}
	}
	BinaryNode *findMini(BinaryNode *t)const{
		if(t==NULL){
			return NULL;
		}
		else if(t->left == NULL){
			return t;
		}
		else
			return findMini(t->left);
	}
	BinaryNode *findMax(BinaryNode *t)const{
		if(t==NULL)
			return NULL;
		else if(t->right=NULL)
			return t;
		else
			return findMax(t->right);
	}
	bool contains(const Comparable&x, BinaryNode* t)const{
		if(t == NULL){
			return false;
		}
		else if(x<t->element){
			return contains(x,t->left);
		}
		else if(x>t->element){
			return contains(x,t->right);
		}
		else
			return true;
	}
	void makeEmpty(BinaryNode *&t){
		if(t != NULL){
			makeEmpty(t->left); 
			makeEmpty(t->right); 
			delete t; 
		}
	}
	void printTree(BinaryNode* t)const{
		if( t== NULL){
			return NULL;
		}
		else{
			std::cout << t->element << std::endl;
			printTree(t->left);
			printTree(t->right);
		}
	}
	BinaryNode* clone(BinaryNode *t)const{
		if(t ==NULL){
			return NULL;
		}
		return new BinaryNode(t->element,clone(t->left),clone(t->right));
	}


public:
	bool contains(const Comparable &x)const{
		return contains(x,root);
		
	}
	int height(BinaryNode *t){
		if( t==NULL)
			return -1; 
		else
			return 1 + max(height(t->left),height(t->right));
	}
	void insert(const Comparable &x){
		insert(x,root);
	}
	void remove(const Comparable &x){
		remove(x,root);
	}
	~BinarySearchTree(){
		makeEmpty(); 
	}
	const BinarySearchTree& operator=(const BinarySearchTree& rhs){
		if(this!=rhs){
			makeEmpty(); 
			root=clone(rhs.root);
		}
		return *this;
	}

};
